#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

SSTable::SSTable()//默认构造函数
{
    length=0;
    origin=nullptr;
}

SSTable::SSTable(int leng,int* ori)//构造函数
{
    length=leng;
    origin=new int[leng];
    for(int i=0;i<leng;i++)
    {
        origin[i]=ori[i];
    }
}

SSTable::~SSTable()//析构函数
{   
    delete[] origin;
}

int SSTable::getLength()
{
    return length;
}

int* SSTable::getOrigin()
{
    return origin;
}

void SSTable::setLength(int leng)//设置长度
{
    length=leng;
}

void SSTable::setOrigin(int* ori)//设置数组
{
    for(int i=0;i<length;i++)
    {
        origin[i]=ori[i];
    }
}

int SSTable::binSearch(int val)//二分查找
{
    int low=0;
    int high=length-1;
    while(low<=high)
    {
        int mid =(low+high)/2;
        if(origin[mid]==val)
        {
            return mid;
        }
        else if (origin[mid]<val)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return -1;
}

BSTreeNode::BSTreeNode()//默认构造函数
{
    data=0;
    lchild=nullptr;
    rchild=nullptr;
}

BSTreeNode::BSTreeNode(int Data)//初始化节点值
{
    data=Data;
    lchild=nullptr;
    rchild=nullptr;
}

BSTreeNode::BSTreeNode(int Data, BSTreeNode* lChild, BSTreeNode* rChild)// 带子节点的构造函数
{
    data=Data;
    lchild=lChild;
    rchild=rChild;
}

BSTreeNode::~BSTreeNode()// 析构函数
{
    delete lchild; // 递归删除左子树
    delete rchild; // 递归删除右子树
}

int BSTreeNode::getData()// 返回节点数据
{
    return data; 
}

BSTreeNode* BSTreeNode::getLChild()// 返回左子节点
{
    return lchild;
}

BSTreeNode* BSTreeNode::getRChild() // 返回右子节点
{
    return rchild; 
}

void BSTreeNode::setData(int Data)// 设置节点数据
{
    data=Data;
}

void BSTreeNode::setLChild(BSTreeNode* lChild)// 设置左子节点
{
    lchild = lChild;
}

void BSTreeNode::setRChild(BSTreeNode* rChild)// 设置右子节点
{
    rchild = rChild;
}

BSTree::BSTree()//默认构造函数
{
    num=0;
    root=nullptr;
}

BSTree::BSTree(int n, int* Data)
{
    num=n;
    root=nullptr;
    if(n>0)
    {
        root=new BSTreeNode(Data[0]);
        for(int i=1;i<n;i++)
        {
            addNode(Data[i]);      
        }
    }
}

BSTree::~BSTree()//析构函数
{
    delete root;
}

int BSTree::getNum()//返回节点数量
{
    return num;
}

BSTreeNode* BSTree::getRoot()//返回根节点
{
    return root;
}

void BSTree::setNum(int n)//设置节点数目
{
    num=n;
}

void BSTree::setRoot(BSTreeNode* Root)//设置根节点
{
    root=Root;
}

void BSTree::printTemp(BSTreeNode* node, string& result)
{
    if (node != nullptr) {
        result += to_string(node->getData()) + " "; // 添加当前节点数据
        printTemp(node->getLChild(), result); // 遍历左子树
        printTemp(node->getRChild(), result); // 遍历右子树
    }
}

string BSTree::printTree()// 前序遍历打印树
{
    string result;
    printTemp(root, result); // 调用私有函数进行遍历
    return result; // 返回遍历结果
}

bool BSTree::searchNode(int val)
{
    return searchNodeHelper(root, val); 
}

bool BSTree::searchNodeHelper(BSTreeNode* node, int val) 
{
    if (node == nullptr) 
    {
        return false; // 如果达到叶子节点，返回false
    }
    if (node->getData() == val) 
    {
        return true; // 找到目标节点，返回true
    } 
    else if (val < node->getData()) 
    {
        return searchNodeHelper(node->getLChild(), val); // 递归搜索左子树
    } 
    else 
    {
        return searchNodeHelper(node->getRChild(), val); // 递归搜索右子树
    }
}


bool BSTree::addNode(int val)//添加节点
{
    if (root == nullptr) 
    {
        root = new BSTreeNode(val); // 如果树为空，创建根节点
        num++;
        return true;
    }
    return addNodeHelper(root, val);
}

bool BSTree::addNodeHelper(BSTreeNode* node, int val) 
{
    if (val < node->getData())
     {
        if (node->getLChild() == nullptr)
         {
            node->setLChild(new BSTreeNode(val)); // 创建左子节点
            num++;
            return true;
        } 
        else 
        {
            return addNodeHelper(node->getLChild(), val); // 递归添加到左子树
        }
    } 
    else if (val > node->getData()) 
    {
        if (node->getRChild() == nullptr)
        {
            node->setRChild(new BSTreeNode(val)); // 创建右子节点
            num++;
            return true;
        } 
        else 
        {
            return addNodeHelper(node->getRChild(), val); // 递归添加到右子树
        }
    } 
    else 
    {
        return false; // 值已存在，不进行添加
    }
}

bool BSTree::deleteNode(int val)//删除节点
{
    return deleteNodeHelper(&root, val); 
}

bool BSTree::deleteNodeHelper(BSTreeNode** node, int val) 
{
    if (*node == nullptr) 
    {
        return false; // 不存在要删除的节点
    }

    if (val < (*node)->getData()) 
    {
        return deleteNodeHelper(&(*node)->lchild, val); // 向左子树递归查找
    } 
    else if 
    (val > (*node)->getData()) 
    {
        return deleteNodeHelper(&(*node)->rchild, val); // 向右子树递归查找
    } 
    else 
    {
        // 找到要删除的节点
        if ((*node)->getLChild() == nullptr) // 只有右子树
        {
            BSTreeNode* temp = *node;
            *node = (*node)->getRChild(); // 提升右子树
            delete temp; // 删除当前节点
        } 
        else if ((*node)->getRChild() == nullptr) // 只有左子树
        {
            BSTreeNode* temp = *node;
            *node = (*node)->getLChild(); // 提升左子树
            delete temp; // 删除当前节点
        } 
        else // 两个子节点都存在
        {
            BSTreeNode* minNode = findMin((*node)->getRChild()); // 找到右子树中的最小节点
            (*node)->setData(minNode->getData()); // 用其值替换当前节点值
            return deleteNodeHelper(&(*node)->rchild, minNode->getData()); // 删除右子树中的最小节点
        }
        num--; // 减少节点计数
        return true; // 删除成功
    }
}
BSTreeNode* BSTree::findMin(BSTreeNode* node) 
{
    while (node->getLChild() != nullptr) 
    {
        node = node->getLChild(); // 不断向左下查找
    }
    return node; // 返回最小节点
}